# 给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
#
#  示例 1：
# 输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
# 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
#
#  示例 2：
# 输入：root = [5,1,7]
# 输出：[1,null,5,null,7]
from com.example.tree.tree_node import TreeNode


class Solution:
    def increasingBST2(self, root: TreeNode) -> TreeNode:
        """
        中序遍历修改节点指向
        遍历到一个节点时，把它的左孩子设为空，并将其本身作为上一个遍历到的节点的右孩子
        :param root:
        :return:
        """
        self.tmpNode = dummpNode = TreeNode(-1)

        def inorder(node) -> None:
            if not node:
                return
            inorder(node.left)

            self.tmpNode.right = node
            node.left = None
            self.tmpNode = node

            inorder(node.right)

        inorder(root)
        return dummpNode.right

    def increasingBST1(self, root: TreeNode) -> TreeNode:
        """
        先中序遍历得到递增的序列，然后构造
        :param root:
        :return:
        """
        res = []

        def inorder(root: TreeNode) -> None:
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)

        if not root:
            return None
        inorder(root)
        newRoot = cur = TreeNode(res[0])
        for i in range(1, len(res)):
            cur.right = TreeNode(res[i])
            cur = cur.right
        return newRoot

    def increasingBST(self, root: TreeNode) -> TreeNode:
        return self.increasingBST2(root)


if __name__ == "__main__":
    root = TreeNode(5)
    root.left, root.right = TreeNode(1), TreeNode(7)
    resRoot = tmp = Solution().increasingBST(root)
    while tmp:
        print(tmp.val)
        tmp = tmp.right
